package leetcode.f1t100;

/**
 * 从0,1矩阵中寻找全部为1最大范围长方形的范围大小
 * https://leetcode.com/problems/maximal-rectangle/
 *
 * @author lichx
 * @createTime 2024/1/30 16:31
 */
public class Q85_MaximalRectangle {

    public static void main(String[] args) {
        Q85_MaximalRectangle bean = new Q85_MaximalRectangle();
        char[][] matrix = {{'1','0','0','0','1'},{'1','1','0','1','1'},{'1','1','1','1','1'}};
        System.out.println(bean.maximalRectangle(matrix));
    }

    public int maximalRectangle(char[][] matrix) {
        int[] arr = new int[matrix[0].length];
        int max = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == '0'){
                    arr[j] = 0;
                } else {
                    arr[j]++;
                }
            }
            max = Math.max(max,largestRectangleArea(arr));
        }
        return max;
    }

    // from Q84
    public int largestRectangleArea(int[] heights) {
        // 左边最近小于当前下标值的下标, 没有则-1
        int[] leftNearIndex = new int[heights.length];
        // 右边最近小于当前下标值的下标, 没有则数组长度
        int[] rightNearIndex = new int[heights.length];
        int point;
        leftNearIndex[0] = -1;

        for (int i = 1; i < heights.length; i++) {
            point = i - 1;
            while (point >= 0 && heights[point] >= heights[i]) {
                point = leftNearIndex[point];
            }
            leftNearIndex[i] = point;
        }
        rightNearIndex[heights.length - 1] = heights.length;
        for (int i = heights.length - 2; i >= 0; i--) {
            point = i + 1;
            while (point <= heights.length - 1 && heights[point] >= heights[i]) {
                point = rightNearIndex[point];
            }
            rightNearIndex[i] = point;
        }
        int area = 0;
        for (int i = 0; i < heights.length; i++) {
            // 面积等于当前位置的高度* (右边最近小于当前位置值下标-左边最近小于当前位置值下标 -1)
            area = Math.max(area, heights[i] * (rightNearIndex[i] - leftNearIndex[i] - 1));
        }
        return area;
    }
}
